package com.matrix.draft.algorithm;

import java.util.Stack;

/**
 * LeetCode第20题: 给定()[]{}字符串, 看看字符串是否有效
 */
public class L20 {

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        for (char ch : s.toCharArray()) {
            stack.push(ch);
            // stack.forEach(System.out::print);
            // System.out.println();
            recursePop(stack);
        }
        return stack.size() == 0;
    }

    void recursePop(Stack stack) {
        if (!needContinue(stack)) {
            return;
        }
        doublePop(stack);
        recursePop(stack);
    }

    boolean needContinue(Stack stack) {
        if(stack.size() < 2){
            return false;
        }
        return new Character('(').equals(stack.get(stack.size() - 2)) && new Character(')').equals(stack.peek()) ||
                (new Character('[').equals(stack.get(stack.size() - 2)) && new Character(']').equals(stack.peek())) ||
                (new Character('{').equals(stack.get(stack.size() - 2)) && new Character('}').equals(stack.peek()));
    }

    void doublePop(Stack stack) {
        stack.pop();
        stack.pop();
    }

    public static void main(String[] args) {
        System.out.println(new L20().isValid("()[(){{}}]"));
    }

}
